package bloomfilter;

import java.util.TreeSet;

/**
 * @Author: LDeng
 * @Date: 2021-04-28 16:25
 */
public class BloomFilter<T> {
    //二进制向量长度（一共有多少个二进制位）
    private int bitSize;

    //二进制向量
    private long[] bits;

    //哈希函数
    private int hashSize;

    /**
     * @param n 数据规模
     * @param p 误判率(0-1)
     */
    public BloomFilter(int n, double p) {
        if (n <= 0 || p <= 0 || p >= 1) {
            throw new IllegalArgumentException("参数错误");
        }
        //套公式求二进制向量长度
        double ln2 = Math.log(2);
        bitSize = (int) (-(n * Math.log(p)) / (ln2 * ln2));
        //求出哈希函数个数
        hashSize = (int) (bitSize * ln2 / n);
        System.out.println("二进制位数:" + bitSize);
        System.out.println("哈希函数个数:" + hashSize);
        //bits数组的长度
        bits = new long[(bitSize + Long.SIZE - 1) / (Long.SIZE)];
        System.out.println("数组长度:"+bits.length);
        //类似分页，
    }

    public void put(T value) {
        notNullCheck(value);
        //value.hashCode()>hash1>索引1
        //value.hashCode()>hash2>索引2
        //value.hashCode()>hash3>索引3...
        int hash1 = value.hashCode();
        int hash2 = hash1 >> 16;

        for (int i = 1; i <= hashSize; i++) {
            int combinedHash = hash1 + (i * hash2);
            if (combinedHash < 0) {
                combinedHash = ~combinedHash;
            }
            //生成二进制位的索引
            int index = combinedHash % bitSize;//取固定长度
            //System.out.println("put: "+index);
            //查询index位置的二进制位是否为0
            //设置index位置的二进制位为1
            set(index);

        }
    }

    public boolean contains(T value) {
        notNullCheck(value);
        int hash1 = value.hashCode();
        int hash2 = hash1 >> 16;

        for (int i = 1; i <= hashSize; i++) {
            int combinedHash = hash1 + (i * hash2);
            if (combinedHash < 0) {
                combinedHash = ~combinedHash;
            }
            //生成二进制位的索引
            int index = combinedHash % bitSize;//取固定长度
            //System.out.println("contains:"+index);
            //查询index位置的二进制位是否为0

            if (!get(index)) return false;
        }
        return true;
    }

    //设置index位置的二进制位为1
    private void set(int index) {
        //找到index对应的long[xxxxxxxx][xxxxxxxx][xxxxxxxx][xxxxxxxx]
        long value = bits[index / Long.SIZE];
        //找到long里面的二进制位
        //将 index%Long.SIZE 位置的值改为1;
        //使用 位或
        /**
         *   1 0 0 0 0 0   原数
         * | 0 0 0 1 0 0   和这个数字位或 1<<2
         * -----------------
         *   1 0 0 1 0 0
         */
        //n|(1<<k) 设置index位置的二进制为1
        bits[index/Long.SIZE] = value | 1 << (index % Long.SIZE);

    }

    //查看index位置的二进制值
    private boolean get(int index) {
        long value = bits[index / Long.SIZE];
        //获取二进制位的值
         //按位与
        /**
         *  1 0 1 0 1 0 1 1 1
         * &0 0 0 0 0 1 0 0 0
         *  -------------------
         *  0 0 0 0 0 0 0 0 0
         */
        return (value&(1<<index%Long.SIZE))!=0;//不等于0返回1
    }


    private void notNullCheck(T value) {
        if (value == null) {
            throw new IllegalArgumentException("数据为空");
        }
    }
}
